package cn.xaut.动态规划;

import java.util.Arrays;

public class demo198 {

    // memo[i] 表示考虑抢劫 nums[i...n-1] 所能获得的最大收益
    int[] memo; 
    
    private int rob3(int[] nums, int index) {
        
        // 递归终止条件
        if (index >= nums.length)
            return 0;
        if (memo[index] != 0)
            return memo[index];
        
        // 递归过程
        for (int i = index; i < nums.length; i++) 
            memo[index] = Math.max(memo[index], nums[i] + rob3(nums, i + 2));

        return memo[index];
    }
    
    // 递归解法（记忆化搜索）(自顶向下探索)
    public int rob3(int[] nums) {
        memo = new int[nums.length];
        return rob3(nums, 0);
    }
    
    private int rob(int[] nums, int index) {
        
        // 递归终止条件
        if (index >= nums.length)
            return 0;
        
        // 递归过程
        int res = 0;
        for (int i = index; i < nums.length; i++) 
            res = Math.max(res, nums[i] + rob(nums, i + 2));
        
        return res;
    }
    
    // 递归解法（时间复杂度高，指数级别）
    public int rob2(int[] nums) {
        return rob(nums, 0);
    }
    
    // 动态规划
    public int rob(int[] nums) {

        int n = nums.length;
        if (n == 1)
            return nums[0];

        // dp[i] 表示偷取 dp[i...n-1] 范围里的房子
        int[] dp = new int[n];

        // 基础状态
        dp[n - 1] = nums[n - 1];
        dp[n - 2] = Math.max(nums[n - 2], nums[n - 1]);

        // 状态转移
        for (int i = n - 3; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                if (j + 2 < n)
                    dp[i] = Math.max(dp[i], nums[j] + dp[j + 2]);
                else
                    dp[i] = Math.max(dp[i], nums[j]);
            }
        }
        return dp[0];
    }
    
    // 改变对状态的定义（动态规划）
    public int rob4(int[] nums) {
        
        int n = nums.length;
        if (n == 0)
            return 0;
        if (n == 1)
            return nums[0];
        
        // dp[0...i] 表示从 0号房屋开始 到 i 号房屋所能窃取的最大价值
        int[] dp = new int[n];
        
        // 基础状态
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        
        // 状态转移
        for (int i = 2; i < n; i++) {
            for (int j = 0; j <= i; j++) 
                dp[i] = Math.max(dp[i], dp[j] + (j + 2 <= i ? nums[j + 2] : 0) );
        }
        
        return dp[n - 1];
    }

    // 改变对状态的定义（记忆化搜索）
    public int rob5(int[] nums) {

        int n = nums.length;
        if (n == 0)
            return 0;
        
        // memo[i] 表示窃取从 0 号到 i 号房屋所能窃取的最大价值
        memo = new int[n];
        Arrays.fill(memo, -1);
        return rob5(nums, n - 1);
    }

    private int rob5(int[] nums, int index) {
        
        // 递归终止条件
        if (index == 0)
            return nums[0];
        if (index == 1)
            return Math.max(nums[1], nums[0]);
        if (memo[index] != -1)
            return memo[index];
        
        // 递归过程
        for (int i = 0; i < index; i++) 
            memo[index] = Math.max(memo[index], rob5(nums, i) + (i + 2 <= index ? nums[i + 2] : 0 ) );
        
        return memo[index];
    }
    
    public static void main(String[] args) {

        System.out.println(new demo198().rob5(new int[]{1, 2, 3, 1}));  // 4
        System.out.println(new demo198().rob5(new int[]{2, 7, 9, 3, 1}));  // 12
        System.out.println(new demo198().rob5(new int[]{2, 1}));  // 2
        System.out.println(new demo198().rob5(new int[]{1, 2}));  // 2
        System.out.println(new demo198().rob5(new int[]{1, 3, 1}));  // 3
    }
}
